package com.example.javamaday.queue;

public class MaxPriorityQueue<T extends Comparable<T>> {

    private T[] items;

    private int N; //记录元素个数

    // 构造方法
    public MaxPriorityQueue(int capacity) {
        this.items = (T[]) new Comparable[capacity + 1];
        this.N = 0;
    }

    public int getSize() {
        return N;
    }

    public boolean isEmpty() {
        return N == 0;
    }

    private boolean less(int i, int j) {
        return items[i].compareTo(items[j]) < 0;
    }

    private void exch(int i, int j) {
        T temp = items[i];
        items[i] = items[j];
        items[j] = temp;
    }

    private void insert(T t) {
        items[++N] = t;
        swim(N);
    }

    public T delMax() {
        T max = items[1];
        exch(1, N);
        N--;
        sink(1);
        return max;
    }

    // 上浮算法，使索引k处的元素处于正确的位置
    public void swim(int k) {
        while (k > 1) {
            if (less(k / 2, k)) {
                exch(k / 2, k);
            }
            k = k / 2;
        }
    }


    // 下沉算法，使索引k处的元素处于正确的位置
    public void sink(int k) {
        while (2 * k <= N) {
            int max;
            // 如果有右子节点
            if (2 * k + 1 <= N) {
                if (less(k * 2, k * 2 + 1)) {
                    max = 2 * k + 1;
                } else {
                    max = 2 * k;
                }
            } else { // 只有左子节点
                max = 2 * k;
            }
            if (!less(k, max)) {  // 找到合适的位置，跳出循环
                break;
            }
            exch(k, max);
            k = max;
        }
    }

    public static void main(String[] args) {
        MaxPriorityQueue<Integer> queue = new MaxPriorityQueue<Integer>(10);
        queue.insert(1);
        queue.insert(6);
        queue.insert(2);
        queue.insert(5);
        queue.insert(3);
        queue.insert(8);
        while (!queue.isEmpty()) {
            System.out.println(queue.delMax());
        }
    }
}
